﻿//1818. 绝对差值和
//给你两个正整数数组 nums1 和 nums2 ，数组的长度都是 n 。
//数组 nums1 和 nums2 的 绝对差值和 定义为所有 | nums1[i] - nums2[i] | （0 <= i < n）的 总和（下标从 0 开始）。
//你可以选用 nums1 中的 任意一个 元素来替换 nums1 中的 至多 一个元素，以 最小化 绝对差值和。
//在替换数组 nums1 中最多一个元素 之后 ，返回最小绝对差值和。因为答案可能很大，所以需要对 109 + 7 取余 后返回。
//| x | 定义为：
//如果 x >= 0 ，值为 x ，或者
//如果 x <= 0 ，值为 - x


class Solution {
public:
    int mod = 1'000'000'007;
    int minAbsoluteSumDiff(vector<int>& nums1, vector<int>& nums2)
    {
        vector<int> arr = nums1;
        sort(arr.begin(), arr.end());
        int sum = 0, x = 0;
        int n = nums1.size();
        for (int i = 0; i < n; i++)
        {
            int diff = abs(nums1[i] - nums2[i]);
            sum = (sum + diff) % mod;
            int j = lower_bound(arr.begin(), arr.end(), nums2[i]) - arr.begin();
            if (j < n)
                x = max(x, diff - (arr[j] - nums2[i]));
            if (j > 0)
                x = max(x, diff - (nums2[i] - arr[j - 1]));
        }
        return (sum - x + mod) % mod;
    }
};